Shift registers are circuits used, for example, in computers, calculators and storage devices that include a cascade-connected series of stages (typically implemented by flip-flops) such that binary data values are shifted from stage to stage in the series.
Linear Feedback Shift Registers (LFSRs) are a type of shift register used, for example, in encryption and fast counter applications. Conventional LFSRs are fixed-length (i.e., a fixed number of flip-flops) shift registers and include a sequence control circuit (typically including an XNOR logic gate) that receives operational state information from several taps in the series of stages, and feeds binary values to the least-significant bit (LSB) stage. Conventional LFSRs are sold as discrete devices, but are also incorporated into programmable logic devices (PLDs) and application specific integrated circuits (ASICs).
The operational state of an LFSR at a point in time is determined by the binary values stored in each stage (e.g., the output signals of its flip-flops) at that point in time. At each CLOCK pulse, data is shifted from one state to the next in the series, thereby creating a sequence of operational states. Each subsequent operational state is controlled by the sequence control circuit, which transmits a binary value to the LSB stage in accordance with the binary values generated at the taps when data is shifted between the stages. Therefore, a sequence of operational states is generated that repeats in a cycle. For a given LFSR, the number and sequence of operational states in this cycle is determined by the number of stages (flip-flops), the number and location of taps and the sequence control circuit logic of the LFSR.
LFSRs are used to form encryption schemes because, when two identical LFSRs are initially in a first operational state, both LFSRs will enter a second operational state after a selected number of data shifts. This facilitates encryption because the cycle of large LFSRs includes millions (or more) of operational states, thereby making it very difficult for a third party to decipher the encryption scheme.
The concepts introduced above are explained in further detail with reference to the simplified LFSR examples shown in FIGS. 1 through 6. These examples depict conventional LFSRs with only four stages for explanatory purposes. LFSRs may be of any length, and often include 128 stages or more when used in encryption applications. Although the conventional LFSRs shown in FIGS. 1 through 6 include only four stages, the following description is consistent with LFSRs having many more stages.
Referring to FIG. 1, LFSR 100 includes four flip-flops 101 through 104 and an XNOR gate 110 that are wired as a shift-right shift register. The Q0 output terminal of flip-flop 101 is connected to the D1 input terminal of flip-flop 102, the Q1 output terminal of flip-flop 102 is connected to the D2 input terminal of flip-flop 103, and the Q2 output terminal of flip-flop 103 is connected to the D3 input terminal of flip-flop 104. The taps of LFSR 100 are located at the Q2 and Q3 output terminals of flip-flops 103 and 104, respectively, and are connected to the input terminals of XNOR gate 110. XNOR gate 110 forms the sequence control circuit of LFSR 100, and transmits an output signal to the DO input terminal of LSB flip-flop 101. The clock input terminal of each flip-flop 101 through 104 receives a CLOCK signal.
During operation, LFSR 100 shifts through fifteen (15) operational states in a sequence that is controlled by the sequence control circuit (XNOR gate 110). If a first operational state is defined when all flip-flops 101 through 104 are reset (i.e., their output signal is binary zero), a subsequent clock pulse causes LFSR 100 to shift the zero values from flip-flops 101 through 103 into flip-flops 102 through 104, respectively. In addition, the zero values in flip-flops 103 and 104 are combined in XNOR gate 110 to generate a binary one output signal that is transmitted to flip-flop 101. The reset operational state and subsequent operational state are respectively entered as operational states 0 (zero) and 1 (one) in Table 1 (below). The remaining operational states 2 through 14 of the cycle associated with LFSR 100 are similarly generated and are also shown below in Table 1.
TABLE 1 ______________________________________ STATE Q3 Q2 Q1 Q0 STATE Q3 Q2 Q1 Q0 ______________________________________ 0 0 0 0 0 8 1 1 0 0 1 0 0 0 1 9 1 0 0 1 2 0 0 1 1 10 0 0 1 0 3 0 1 1 1 11 0 1 0 1 4 1 1 1 0 12 1 0 1 0 5 1 1 0 1 13 0 1 0 0 6 1 0 1 1 14 1 0 0 0 7 0 1 1 0 ______________________________________
FIG. 2 shows a four-bit LFSR 200 in which the sequence control circuit is modified to generate sixteen operational states. LFSR 200 includes flip-flops 201 through 204, a three-input XNOR gate 210 and a three input AND gate 220. XNOR gate 210 and AND gate 220 form the sequence control circuit of LFSR 200. Similar to LFSR 100, the Q0 output terminal of LSB flip-flop 201 is connected to the D1 input terminal of flip-flop 202, the Q1 output terminal of flip-flop 202 is connected to the D2 input terminal of flip-flop 203, and the Q2 output terminal of flip-flop 203 is connected to the D2 input terminal of flip-flop 204. The output terminals Q0, Q1 and Q2 of flip-flops 201, 202 and 203 are respectively connected to the input terminals of AND gate 220. In addition, the output terminals Q2 and Q3 of flip-flops 203 and 204 are connected to two of the three input terminals of XNOR gate 210, and the output terminal of AND gate 220 is connected to the third input terminal of XNOR gate 210. The output terminal of XNOR gate 210 is connected to the D0 input terminal of flip-flop 201. The clock input terminal of each flip-flop 201 through 204 receives a CLOCK signal.
LFSR 200 operates in a manner similar to LFSR 100, and generates a similar sequence of operational states. However, LFSR 200 differs from LFSR 100 in that it utilizes AND gate 220 to enter and exit an additional 1,1,1,1 operation state (LFSR 100 does not enter this state). This additional operational state increases the number of operational states in the cycle associated with LFSR 200 to sixteen. The sequence of sixteen operational states in this cycle is shown in Table 2 (below). A comparison of the sequence in Table 2 with that of Table 1 shows that the sequence of Table 2 inserts the additional 1,1,1,1 state as state 4. All subsequent operational states of the sequence are shifted by one position.
TABLE 2 ______________________________________ STATE Q3 Q2 Q1 Q0 STATE Q3 Q2 Q1 Q0 ______________________________________ 0 0 0 0 0 8 0 1 1 0 1 0 0 0 1 9 1 1 0 0 2 0 0 1 1 10 1 0 0 1 3 0 1 1 1 11 0 0 1 0 4 1 1 1 1 12 0 1 0 1 5 1 1 1 0 13 1 0 1 0 6 1 1 0 1 14 0 1 0 0 7 1 0 1 1 15 1 0 ______________________________________
An LFSR can be made to count in the opposite direction ("down") by advancing the taps by one flip-flop, and by wiring the flip-flops in an opposite order to that shown in FIGS. 1 and 2. Examples of such "down-counting" LFSRs are shown in FIGS. 3 and 4.
Referring to FIG. 3, LFSR 300 includes four flip-flops 301 through 304 and an XNOR gate 310 that are wired as a shift-left shift register. The Q3 output terminal of flip-flop 304 is connected to the D2 input terminal of flip-flop 303, the Q2 output terminal of flip-flop 303 is connected to the D1 input terminal of flip-flop 302, and the Q1 output terminal of flip-flop 302 is connected to the D0 input terminal of flip-flop 301. The output terminals Q0 and Q3 of flip-flops 301 and 304 are connected to the input terminals of XNOR gate 310. The output signal from XNOR gate 310 is transmitted to the D3 input terminal of LSB flip-flop 304.
During operation, LFSR 300 cycles through 15 (fifteen) operational states in a sequence that is opposite to that of LFSR 100 (discussed above). For example, if a first operational state is defined when all flip-flops 301 through 304 are reset, a subsequent clock pulse causes LFSR 300 to shift the zero values from flip-flops 302 through 304 into flip-flops 301 through 303, respectively. In addition, the zero values in flip-flops 301 and 304 are combined in XNOR gate 310 to generate a binary one output signal that is transmitted to flip-flop 304. Therefore, LFSR shifts from the reset operational state to a 0,0,0,1 state, which is opposite to that associated with the sequence of LFSR 100. The remaining operational states of LFSR 300 are also opposite to that those shown in Table 1 (above).
FIG. 4 shows a left-shifting four-bit LFSR 400 that has sixteen operational states. LFSR 400 includes flip-flops 401 through 404, a three-input XNOR gate 410 and a three input AND gate 420. Similar to LFSR 300 (see FIG. 3), the Q3 output terminal of flip-flop 404 is connected to the D2 input terminal of flip-flop 403, the Q2 output terminal of flip-flop 403 is connected to the D1 input terminal of flip-flop 402, and the Q1 output terminal of flip-flop 402 is connected to the D0 input terminal of flip-flop 401. The output terminals Q1, Q2 and Q3 of flip-flops 402, 403 and 404 are connected the input terminals of AND gate 420. In addition, the output terminals Q0 and Q3 of flip-flops 401 and 404 are connected to two of the three input terminals of XNOR gate 410, and the output of AND gate 420 is connected to the third input terminal of XNOR gate 410. The output terminal of XNOR gate 410 is connected to the D3 input terminal of flip-flop 404.
LFSR 400 operates in a manner similar to LFSR 300, and generates a similar sequence of operational states. However, LFSR 400 differs from LFSR 300 in that it utilizes AND gate 420 to enter and exit a 1,1,1,1 operation state (LFSR 300 does not enter this state). This additional operational state increases the number of operational states entered by LFSR 400 to sixteen.
An LFSR can also be built to count both up and down by inserting multiplexers in the shift chain and including both the up- and down-counting circuitry as inputs to the least-and most-significant bits in the shift register. FIG. 5 shows an example of a four-bit bi-directional (up/down) LFSR 500 with a maximal counting sequence length (16 states). Referring to FIG. 5, LFSR 500 includes flip-flops 501 through 504, a first three-input XNOR gate 510, a second three-input XNOR gate 511, a first three input AND gate 520, a second three input AND gate 521, and two-input multiplexers 530 through 533. The Q0 output terminal of flip-flop 501 is connected to a first input terminal of multiplexer 531 and to input terminals of XNOR gate 511 and AND gate 520. The Q1 output terminal of flip-flop 502 is connected to a first input terminal of multiplexer 532 and a second input terminal of multiplexer 530. The Q2 output terminal of flip-flop 503 is connected to a first input terminal of multiplexer 533 and a second input terminal of multiplexer 531, and is also connected to input terminals of XNOR gate 510 and AND gates 520 and 521. The Q3 output terminal of flip-flop 504 is connected to the second input terminal of multiplexer 532 and to input terminals of XNOR gates 510 and 511 and AND gate 521. The select input terminals of multiplexers 530 through 533 are controlled by an UP/DOWN signal. When the UP/DOWN signal indicates a count-up mode, signals are passed through the first input terminals of multiplexers 530 through 533 such that LFSR 500 operates in a manner consistent with LFSR 200 (discussed above). In a count-down mode, signals are passed through the second input terminals of multiplexers 530 through 533 such that LFSR 500 operates in a manner consistent with LFSR 400 (discussed above).
LFSRs can also be made to sequence through a number of states whose length is less than 2.sup.n or 2.sup.n -1 (i.e., to reset after a predetermined number of operational states). A conventional sequence control circuit used to omit (skip) operational states in an LFSR is described in "Build Better Sequential Circuits", Hackett and Leach, ASIC & EDA, March 1992. FIG. 6 shows an example of a 4-bit LFSR 600 that incorporates a sequence control circuit such that its sequence includes only 10 states instead of 15 or 16. In particular, LFSR 600 includes flip-flops 601 through 604, a three-input XNOR gate 610, a three input NAND gate 620 (with two inverted input terminals), and a three input AND gate 630. Three-input XNOR gate 610 and three input NAND gate 620 form the sequence control circuit of LFSR 600. The Q0 output terminal of flip-flop 601 is connected to the D1 input terminal of flip-flop 602, and to the first inverted input terminal of AND gate 620. The Q1 output terminal of flip-flop 602 is connected to the D2 input terminal of flip-flop 603, and to the second inverted input terminal of AND gate 620. The Q2 output terminal of flip-flop 603 is connected to the D3 input terminal of flip-flop 604, to the non-inverted input terminal of NAND gate 620, and to a first input terminal of XNOR gate 610. The Q3 output terminal of flip-flop 604 is connected to the second input terminal of XNOR gate 610. The output terminals of XNOR gate 610 and NAND gate 620 are connected to the input terminals of AND gate 630, whose output terminal is connected to the D0 input terminal of flip-flop 601. With this construction, LFSR 600 generates the sequence shown Table 3 (below). This sequence is the same as that shown in Table 1, except that states 9 through 13 of Table 1 are omitted. In particular, AND gate 630 detects state 8 and resets flip-flop 601 to 0 instead of 1, thus skipping states 9 through 13 of Table 1.
TABLE 3 ______________________________________ STATE Q3 Q2 Q1 Q1 STATE Q3 Q2 Q1 Q0 ______________________________________ 0 0 0 0 0 5 1 1 0 1 1 0 0 0 1 6 1 0 1 1 2 0 0 1 1 7 0 1 1 0 3 0 1 1 1 8 1 1 0 0 4 1 1 1 0 9 1 0 0 0 ______________________________________
A problem associated with conventional shift registers is that it is possible for third parties to utilize reverse engineering to copy an LFSR design and/or to decipher the encryption scheme defined by the LFSR. Specifically, by utilizing well-known reverse engineering techniques to identify the connections between the flip-flops, the number and location of the taps, and the types of logic gates associated with an LFSR, it is possible for a third party to reconstruct the LFSR. With this knowledge, it is possible for the third party to identify the encryption scheme utilized in the LFSR.
What is needed is a programmable shift register that cannot be reverse engineered to identify the underlying encryption scheme used with the LFSR.